package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-16 15:49
 * @description: Functions of this class is
 * 官方题解：
 *class Solution {
 *     public int movingCount(int m, int n, int k) {
 *         if (k == 0) {
 *             return 1;
 *         }
 *         Queue<int[]> queue = new LinkedList<int[]>();
 *         // 向右和向下的方向数组
 *         int[] dx = {0, 1};
 *         int[] dy = {1, 0};
 *         boolean[][] vis = new boolean[m][n];
 *         queue.offer(new int[]{0, 0});
 *         vis[0][0] = true;
 *         int ans = 1;
 *         while (!queue.isEmpty()) {
 *             int[] cell = queue.poll();
 *             int x = cell[0], y = cell[1];
 *             for (int i = 0; i < 2; ++i) {
 *                 int tx = dx[i] + x;
 *                 int ty = dy[i] + y;
 *                 if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
 *                     continue;
 *                 }
 *                 queue.offer(new int[]{tx, ty});
 *                 vis[tx][ty] = true;
 *                 ans++;
 *             }
 *         }
 *         return ans;
 *     }
 *
 *     private int get(int x) {
 *         int res = 0;
 *         while (x != 0) {
 *             res += x % 10;
 *             x /= 10;
 *         }
 *         return res;
 *     }
 * }*
 **/
public class NoNo机器人的运动范围类似于岛屿面积 {
    public static void main(String args[]){

    }

    public int movingCount(int m, int n, int k) {
        boolean vis[][] = new boolean[m][n];
        return dfs(0, 0, m, n, vis, k);
    }

    private int dfs(int i, int j, int m, int n, boolean vis[][], int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || vis[i][j] || (i % 10 + i / 10 + j % 10 + j / 10) > k) {
            return 0;
        }
        vis[i][j] = true;
        return dfs(i + 1, j, m, n, vis, k) + dfs(i, j + 1, m, n, vis, k) +
                dfs(i - 1, j, m, n, vis, k) + dfs(i, j - 1, m, n, vis, k) + 1;
    }

}